package leetcode.problem.q912_sort;

import java.util.Arrays;

public class SortArray {

	public static void main(String[] args) {
		//int[] a = {72, 6, 57, 88, 60, 42, 83, 73, 42, 48, 85};
		int[] a = {72, 6, 57, 88, 60, 42};
        System.out.println(Arrays.toString(a));
        new Solution().sortArray(a);
        System.out.println(Arrays.toString(a));
        
	}

}


class Solution {
    public int[] sortArray(int[] nums) {
    	this.quiskSort(nums, 0, nums.length-1);
    	return nums;
    }
    
    /**
     * 选择基数x
     * 第一轮在于将小于x的数放到基数左边，大于x的数放到基数的右边。
     * 具体实践中，往往通过左右两个指针来和基数对比，然后交换两个指针所指位置的值。
     * 需要注意的是左右两个指针是和基数的值相比，选择的基数是个值，而不是对应的下标
     * @param nums
     * @param start
     * @param end
     */
    public void quiskSort(int[] nums, int start, int end) {
    	int i = start;
    	int j = end;
    	
    	int x = nums[i];
    	
    	while(i<j) {
    		
    		while(i<j) {
    			if(nums[j] < x) {
    				nums[i] = nums[j];
    				break;
    			}
    			j--;
    		}
    		
    		while(i<j) {
    			if(nums[i] > x) {
    				nums[j] = nums[i];
    				break;
    			}
    			i++;
    		}
    	}
    	nums[i] = x;
    	
		if(start < i-1) {
			quiskSort(nums, start, i-1);
		}
	
		if(i+1 < end) {
			quiskSort(nums, i+1, end);
		}
    	
    }
    
    /**
     * 桶排序
     * 
     * https://www.cnblogs.com/lfri/p/9885218.html
     * 
     * @param nums
     * @param start
     * @param end
     */
    public void bucketSort(int[] nums, int start, int end) {
    	
    }
    
    /**
     * 堆排序（Heapsort）
     * 
     * https://www.cnblogs.com/ayqy/p/4052646.html
     * 
     * @param nums
     * @param start
     * @param end
     */
    public void heapSort(int[] nums, int start, int end) {
    	
    }
}

